package 动态规划;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 打家劫舍.java
 * @Description TODO
 * @createTime 2020年11月16日 14:28:00
 * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
 *
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：[1,2,3,1]
 * 输出：4
 * 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
 *      偷窃到的最高金额 = 1 + 3 = 4 。
 *dp[i]=max{dp[i-1],dp[i-2]+nums[i]}
 * 考研优化空间  用两个变量来代替dp数组
 */
public class 打家劫舍 {
    class Solution {
        public int rob(int[] nums) {
            if (nums == null || nums.length == 0) {
                return 0;
            }
            int length = nums.length;
            if (length == 1) {
                return nums[0];
            }
            int[] dp = new int[length];
            dp[0] = nums[0];
            dp[1] = Math.max(nums[0], nums[1]);
            for (int i = 2; i < length; i++) {
                dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
            }
            return dp[length - 1];
        }
    }

    //进行空间优化 因为只需要用到当前元素的前两个元素的值
    class Solution1 {
        public int rob(int[] nums) {
            int prev = 0;
            int curr = 0;

            // 每次循环，计算“偷到当前房子为止的最大金额”
            for (int i : nums) {
                // 循环开始时，curr 表示 dp[k-1]，prev 表示 dp[k-2]
                // dp[k] = max{ dp[k-1], dp[k-2] + i }
                int temp = Math.max(curr, prev + i);
                prev = curr;
                curr = temp;
                // 循环结束时，curr 表示 dp[k]，prev 表示 dp[k-1]
            }

            return curr;
        }
    }


}
